//给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
//
// candidates 中的每个数字在每个组合中只能使用 一次 。
//
// 注意：解集不能包含重复的组合。
//
//
//
// 示例 1:
//
//
//输入: candidates = [10,1,2,7,6,1,5], target = 8,
//输出:
//[
//[1,1,6],
//[1,2,5],
//[1,7],
//[2,6]
//]
//
// 示例 2:
//
//
//输入: candidates = [2,5,2,1,2], target = 5,
//输出:
//[
//[1,2,2],
//[5]
//]
//
//
//
// 提示:
//
//
// 1 <= candidates.length <= 100
// 1 <= candidates[i] <= 50
// 1 <= target <= 30
//
//
// Related Topics 数组 回溯 👍 1537 👎 0

// leetcode submit region begin(Prohibit modification and deletion)
package main

import "sort"

func combinationSum2(candidates []int, target int) [][]int {
	var res [][]int
	var list []int
	var helper func(target int, index int)
	used := make(map[int]bool)
	sort.Ints(candidates)
	helper = func(target int, index int) {
		if target == 0 {
			tmp := make([]int, len(list))
			copy(tmp, list)
			res = append(res, tmp)
			return
		} else if target < 0 {
			return
		}

		for i := index; i < len(candidates); i++ {
			if i > index && candidates[i] == candidates[i-1] && !used[i-1] {
				continue
			}

			used[i] = true
			list = append(list, candidates[i])
			helper(target-candidates[i], i+1)
			list = list[:len(list)-1]
			used[i] = false
		}
	}
	helper(target, 0)
	return res
}

// leetcode submit region end(Prohibit modification and deletion)
